package day_6_26;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main2 {
    /**
     * 40. 组合总和 II
     * https://leetcode.cn/problems/combination-sum-ii/description/
     */
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int t;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        t = target;
        // 先进行排序
        Arrays.sort(candidates);

        dfs(candidates,0,0);

        return ret;
    }

    public void dfs(int[] candidates,int pos,int sum) {
        if(sum == t) {
            ret.add(new ArrayList<>(path));
            return;
        }

        if(sum > t || pos == candidates.length) {
            return;
        }

        for(int i = pos;i < candidates.length;i++) {
            if(i > pos && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            dfs(candidates,i + 1,sum + candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}
